//
// Created by last on 2025/9/11.
//
#ifndef SORTINGTEMPLATE_SORTER_HPP
#define SORTINGTEMPLATE_SORTER_HPP

#include <functional>
#include <stdexcept>
#include <iterator>
#include <type_traits>
#include <cstddef>
#include <array>
#include <utility>
#include <memory>

// 排序顺序枚举
enum class SortOrder
{
    ASC, // 升序
    DESC // 降序
};

// 类型特征检测工具
namespace sorter_detail
{
    // 检测类型是否有 size() 方法
    template <typename T, typename = void>
    struct has_size_method : std::false_type
    {};

    template <typename T>
    struct has_size_method<T, std::void_t<decltype(std::declval<T>().size())>>
        : std::true_type
    {};

    template <typename T>
    inline constexpr bool has_size_method_v = has_size_method<T>::value;

    // 检测类型是否是原始数组或std::array
    template <typename T>
    struct is_primitive_array : std::false_type
    {};

    template <typename T, std::size_t N>
    struct is_primitive_array<T[N]> : std::true_type
    {};

    template <typename T>
    inline constexpr bool is_primitive_array_v = is_primitive_array<T>::value;

    // 检查类型是否支持小于比较
    template <typename T>
    constexpr bool has_less_operator()
    {
        if constexpr (std::is_arithmetic_v<T>)
        {
            return true;
        }
        else
        {
            return requires(const T& a, const T& b)
            {
                { a < b } -> std::convertible_to<bool>;
            };
        }
    }

    // 检查类型是否支持大于比较
    template <typename T>
    constexpr bool has_greater_operator()
    {
        if constexpr (std::is_arithmetic_v<T>)
        {
            return true;
        }
        else
        {
            return requires(const T& a, const T& b)
            {
                { a > b } -> std::convertible_to<bool>;
            };
        }
    }

    // 获取容器大小的实现
    template <typename Array>
    constexpr size_t get_container_size_impl(Array& arr)
    {
        using RawType = std::remove_reference_t<Array>;

        if constexpr (is_primitive_array_v<RawType>)
        {
            return std::extent_v<RawType>;
        }
        else if constexpr (has_size_method_v<Array>)
        {
            return arr.size();
        }
        else
        {
            static_assert(
                is_primitive_array_v<RawType> ||
                has_size_method_v<Array>,
                "传入容器须具有 size() 方法"
            );
            return 0;
        }
    }

    // 插入排序实现（用于小数组优化）
    template <typename Array, typename Compare>
    void insertion_sort(Array& arr, size_t low, size_t high, Compare comp)
    {
        for (size_t i = low + 1; i <= high; ++i)
        {
            auto key = std::move(arr[i]);
            size_t j = i;

            while (j > low && comp(key, arr[j - 1]))
            {
                arr[j] = std::move(arr[j - 1]);
                --j;
            }
            arr[j] = std::move(key);
        }
    }
} // namespace sorter_detail

// 主排序器类
template <typename Array>
class Sorter
{
private:
    Array& _arr;
    size_t _size;
    static constexpr size_t INSERTION_SORT_THRESHOLD = 16;

    // 快速排序实现（小数组优化）
    template <typename Compare>
    void quicksort_impl(size_t low, size_t high, Compare comp)
    {
        // 添加边界检查
        if (low >= high) return;

        // 小数组使用插入排序
        if (high - low < INSERTION_SORT_THRESHOLD)
        {
            sorter_detail::insertion_sort(_arr, low, high, comp);
            return;
        }

        // 选择三数中值作为枢轴
        size_t mid = low + (high - low) / 2;
        if (comp(_arr[high], _arr[low]))
            std::swap(_arr[low], _arr[high]);
        if (comp(_arr[mid], _arr[low]))
            std::swap(_arr[low], _arr[mid]);
        if (comp(_arr[high], _arr[mid]))
            std::swap(_arr[mid], _arr[high]);

        // 分区
        size_t pi = partition_impl(low, high, comp);

        // 递归排序 - 添加防止无限递归的检查
        if (pi > low) // 确保左分区有元素
            quicksort_impl(low, pi - 1, comp);
        if (pi < high) // 确保右分区有元素
            quicksort_impl(pi + 1, high, comp);
    }

    // 分区函数实现
    template <typename Compare>
    size_t partition_impl(size_t low, size_t high, Compare comp)
    {
        // 添加边界检查
        if (low >= high) return low;

        auto pivot = std::move(_arr[high]);
        size_t i = low;

        for (size_t j = low; j < high; j++)
        {
            if (comp(_arr[j], pivot))
            {
                std::swap(_arr[i], _arr[j]);
                i++;
            }
        }
        _arr[high] = std::move(_arr[i]);
        _arr[i] = std::move(pivot);
        return i;
    }

    // 检查数组有效性
    void check_array_validity() const
    {
        if (_size == 0)
        {
            throw std::invalid_argument("数组长度不能为 0");
        }

        // 检查是否支持索引操作
        static_assert(requires(Array a, size_t i) { a[i]; },
                      "传入数组必须支持索引操作");

        // 检查元素类型是否支持比较操作
        static_assert(sorter_detail::has_less_operator<value_type>(),
                      "数组元素必须支持比较操作");

        // 检查元素类型是否支持大于比较操作（用于降序排序）
        static_assert(sorter_detail::has_greater_operator<value_type>(),
                      "数组元素必须支持大于比较操作（用于降序排序）");
    }

    // 获取容器大小
    static constexpr size_t get_container_size(Array& arr)
    {
        return sorter_detail::get_container_size_impl(arr);
    }

public:
    using value_type = std::remove_reference_t<decltype(_arr[0])>;

    // 删除拷贝和移动操作
    Sorter& operator=(const Sorter&) = delete;
    Sorter& operator=(Sorter&&) = delete;
    Sorter(const Sorter&) = delete;
    Sorter(Sorter&&) = delete;

    // 构造函数 - 显式指定大小
    Sorter(Array& arr, size_t size)
        : _arr(arr), _size(size)
    {
        check_array_validity();
    }

    // 构造函数 - 自动检测容器大小
    explicit Sorter(Array& arr)
        : _arr(arr), _size(get_container_size(arr))
    {
        check_array_validity();
    }

    // 使用自定义比较函数的排序
    template <typename Compare = std::less<value_type>>
    void sort(Compare comp = Compare())
    {
        if (_size > 1)
        {
            quicksort_impl(0, _size - 1, comp);
        }
    }

    // 使用预设排序顺序的排序
    void sort(SortOrder order = SortOrder::ASC)
    {
        if (order == SortOrder::ASC)
        {
            sort(std::less<value_type>());
        }
        else
        {
            sort(std::greater<value_type>());
        }
    }

    // 检查数组是否已排序
    template <typename Compare = std::less<value_type>>
    bool is_sorted(Compare comp = Compare()) const
    {
        for (size_t i = 1; i < _size; ++i)
        {
            if (comp(_arr[i], _arr[i - 1]))
            {
                return false;
            }
        }
        return true;
    }

    // 检查数组是否已按升序排序
    [[nodiscard]] bool is_asc_sorted() const
    {
        return is_sorted(std::less<value_type>());
    }

    // 检查数组是否已按降序排序
    [[nodiscard]] bool is_desc_sorted() const
    {
        return is_sorted(std::greater<value_type>());
    }

    // 获取数组大小
    [[nodiscard]] constexpr size_t size() const noexcept { return _size; }
};


#endif // SORTINGTEMPLATE_SORTER_HPP